%%% shuffle the list
-module(shuffle).
-compile(export_all).
-define(DEBUG(F, D), io:format(F, D)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Fisher-Yates shuffle
%% http://www.itl.nist.gov/div897/sqg/dads/HTML/fisherYatesShuffle.html
shuffle_v1([]) ->
    [];
shuffle_v1(L = [_]) ->
    L;
shuffle_v1(L) ->
    shuffle1(1, L, length(L)).

shuffle1(Len, L, Len) ->
    %?DEBUG("arg is:~p ~p ~p~n", [Len, L, Len]),
    L;
shuffle1(Cur, L, Len) ->
    %?DEBUG("arg is:~p ~p ~p~n", [Cur, L, Len]),
    S = Cur + round((Len - Cur) * random:uniform()),
    %?DEBUG("Select is:~p ~n", [S]),
    L2 = swap_element(L, Cur, S),
    shuffle1(Cur + 1, L2, Len).

swap_element(L, N, N) ->
    L;
swap_element(L, N1, N2) ->
    Z = lists:zip(lists:seq(1, length(L)), L),
    {value, E1} = lists:keysearch(N1, 1, Z),
    {value, E2} = lists:keysearch(N2, 1, Z),
    Z2 = lists:keyreplace(N1, 1, 
                    lists:keyreplace(N2, 1, Z, E1),
                    E2),
    {_, Result} = lists:unzip(Z2),
    Result.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 shuffle_v2(List0) ->
        List1 = [{random:uniform(), X} || X <- List0],
        List2 = lists:keysort(1, List1),
        {_, R} = lists:unzip(List2),
        R.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% shuffle(List1) -> List2
%% Takes a list and randomly shuffles it. Relies on random:uniform
%%
shuffle_v3(List) ->
    %% Determine the log n portion then randomize the list.
    randomize(round(math:log(length(List)) + 0.5), List).

randomize(1, List) ->
    randomize(List);
randomize(T, List) ->
    lists:foldl(fun(_E, Acc) ->
                        randomize(Acc)
                end, randomize(List), lists:seq(1, (T - 1))).

randomize(List) ->
    D = lists:map(fun(A) ->
                          {random:uniform(), A}
                  end, List),

    {_, D1} = lists:unzip(lists:keysort(1, D)),
    D1. 
